package com.Questions.hash;

import java.util.*;
/**
 * 设计哈希集合
 */
public class leetcode705 {
    // 不使用 任何内建的哈希表库设计一个哈希集合
    class MyHashSet {
        private static final int BASE=769;
        private  LinkedList[] data;
        public MyHashSet(){
            data = new LinkedList[BASE];
            for( int i = 0; i < BASE; ++i){// 初始化每一个链式地址
                data[i] = new LinkedList<Integer>();
            }
        }

        public void add(int key){
            int h=hash(key);
            Iterator<Integer> iterator=data[h].iterator();
            while (iterator.hasNext()){
                Integer element = iterator.next();
                if(element == key) {// 哈希集合中已经存在该元素
                    return;
                }
            }
            data[h].offerLast(key);
        }

        public void remove(int key) {
            int h = hash(key);
            Iterator<Integer> iterator = data[h].iterator();
            while (iterator.hasNext()){
                Integer element = iterator.next();
                if(element == key){
                    data[h].remove(element);
                    /*
                    调试经验 remove 一般有两个常用的重载
                     一个是泛型的类型作为参数 这种是找到第一个值相等的对象进行删除
                     一种 是int作为参数 将下标位为参数的记录删除
                     在Integer作为泛型的时候需要注意
                     */
                    return;
                }
            }
        }

        public boolean contains(int key){
            int h = hash(key);
            Iterator<Integer> iterator = data[h].iterator();
            while (iterator.hasNext()) {
                Integer element = iterator.next();
                if (element == key) {
                    return true;
                }
            }
            return false;
        }

        private static int hash(int key){
            return key % BASE;
        }
    }
}
